from collections import defaultdict


"""
吐血，我的滑动超时了
"""


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        left = 0
        right = 0
        dic = defaultdict(int)
        is_valid = False
        want = defaultdict(int)
        for i in t:
            want[i] += 1

        def valid():
            nonlocal is_valid
            for i in t:
                if i not in dic:
                    return False
                if dic[i] < want[i]:
                    return False
            else:
                is_valid = True
                return True
        string = s
        while right < len(s):
            # 先找最大子串
            if s[right] in t:
                dic[s[right]] += 1
            # right+1, 直到符合条件
            while valid():
                string = s[left: right +
                           1] if len(string) > right - left + 1 else string
                # 符合条件，开始增加left
                dic[s[left]] -= 1
                left += 1
            right += 1
        if is_valid:
            return string
        else:
            return ""


def test():
    R = "BANC"
    S = "ADOBECODEBANC"
    T = "ABC"
    assert Solution().minWindow(S, T) == R


def test1():
    R = "ABC"
    S = "ABCDEFACDB"
    T = "ABC"
    assert Solution().minWindow(S, T) == R


def test2():
    R = ""
    S = "ABCDEFACDB"
    T = "ABCG"
    assert Solution().minWindow(S, T) == R


def test3():
    R = ""
    S = "ABCDEFACDB"
    T = ""
    assert Solution().minWindow(S, T) == R


def test4():
    R = "aa"
    S = "aa"
    T = "aa"
    assert Solution().minWindow(S, T) == R


def test5():
    R = ""
    S = "a"
    T = "aa"
    assert Solution().minWindow(S, T) == R


if __name__ == "__main__":
    S = "ADOBECODEBANC"
    T = "ABC"
    print(Solution().minWindow(S, T))
